package main.leetcode.primary.from101to200;

import main.datastruc.ListNode;

/**
 * 142. 环形链表 II 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * <p>为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 *
 * <p>说明：不允许修改给定的链表。
 *
 * <p>进阶： 你是否可以不用额外空间解决此题？
 */
public class ex142 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(new ex142().detectCycle(node1));
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode node = getMeetNode(head);
        if (node == null) {
            return null;
        }
        ListNode tmp = head;
        while (tmp != node) {
            tmp = tmp.next;
            node = node.next;
        }
        return tmp;
    }

    private ListNode getMeetNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head /*.next*/;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }
}
